package others;

import java.util.Arrays;

public class Test923 {
    /**
     * 三数和返回个数
     * 给定一个整数数组arr，以及一个整数target作为目标值，返回满足 i < j < k 且arr[i] + arr[j] + arr[k] == target的元组i, j, k的数量。
     * <p>
     * 由于结果会非常大，请返回 109+ 7的模。
     */
    public static int threeSumMulti(int arr[], int target) {
        Arrays.sort(arr);
        int len = arr.length;
        long count = 0;

        for (int i = 0; i < len; ++i) {

            int left = i + 1;
            int right = len - 1;
            int sum = target - arr[i];
            while (left < right) {

                if (sum < arr[right] + arr[left]) {
                    right--;
                } else if (sum > arr[right] + arr[left]) {
                    left++;
                } else {
                    if (arr[left] == arr[right]) {
                        //排列组合公式
                        count += (right - left + 1) * (right - left) / 2;
                        count %= 1000000007;
                        break;
                    } else {
                        //记录 当左指针与右指针不相等同时又存在多个相同得左指针、右指针 则count = a*b/2
                        int a = 1;
                        int b = 1;
                        while (right > left + 1 && arr[left + 1] == arr[left]) {
                            a++;
                            left++;
                        }
                        while (right - 1 > left && arr[right - 1] == arr[right]) {
                            b++;
                            right--;
                        }
                        count += a * b % 1000000007;
                        left++;
                        right--;
                    }
                }
            }
        }

        return (int) count;
        //最好理解得方法，三层暴力破解
//            for ( int j = i+1; j < len; j++) {
//                int k = len-1;
//                while (k > j){
//                    if(k==j){continue;}
//                    int sum = arr[i] + arr[j] + arr[k];
//                    if(sum == target ){
//                        count ++;
//                        count %= 1000000007;
//                        k--;
//                    }
//
//                }
    }

    public static void main(String[] args) {
        int[] targetArr = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5};
        for (int i = 0; i < targetArr.length; i+=2) {
            System.out.println(i);

        }
//        int i = threeSumMulti(targetArr, 8);


    }
}
